Manifests represent a mapping of strings to references (see \ref{sec:collections}). The primary purpose is to implement document collections (websites) on swarm and enable URL-based addressing of content. This section defines the data structures relevant for manifests as well as the algorithms for lookup and update which implement the manifest API (see \ref{sec:manifests-ux} and \ref{spec:api:manifest}).

A manifest entry can be conceived of as metadata about a file pointed to and retrievable by its reference (see \ref{spec:format:files}). The metadata is quite diverse, ranging from information needed for access control, file information similar to one given on file systems, information needed for erasure coding (see \ref{sec:erasure}, \ref{sec:headers} and \ref{spec:format:erasure}), information for browser, i.e.,  response headers such as content type (MIME info) and most importantly the reference to the file. Using manifests as simple key-value store is exemplified by access control (see \ref{sec:access-control}, \ref{sec:access-control-ux} for discussion as well as \ref{spec:format:access-control} and \ref{spec:api:access-control} for the specification).

\begin{definition}[Manifest entry]\label{def:manifest-entry}
\begin{lstlisting}[language=buzz1]
// /manifest

// manifest entry encodes attributes 
define type entry 
    file/info              // FS file/dir info
    access/params          // access control params
    crs/params             // erasure coding - CRS params
    reference              // reference
    headers                // http response headers 

define type headers
    content.type  [segment size]byte

\end{lstlisting}
\end{definition}

\begin{definition}[Manifest data structure]\label{def:manifests}
\begin{lstlisting}[language=buzz1]
// /manifest

define type node 
    entry  *entry          // reference to chunk serialised as entry
    forks  [<<256]fork     // sparse array of max 256 fork

// fork encodes a branch
define type fork 
    prefix segment   // compaction 
    node   *node     // reference to chunk serialised as node

\end{lstlisting}
\end{definition}

\begin{definition}[Manifest API: path lookup]\label{def:manifests-lookup}
\begin{lstlisting}[language=buzz1]
// /manifest

define function lookup @path []byte
    in *node
has api GET on "/manifest/<@node:reference>/<@path>"
as 
    context access = @node entry access/params 
    // manifest is  a compacted trie
    @fork = @node forks at head @path 
    // if @path empty, the  paths matched return the entry
    if no @path then 
        return @node entry

    if @fork prefix is prefix of @path then // including == 
      return self @path from @fork prefix length
          in @fork node 
   fail with "not found"

\end{lstlisting}
\end{definition}


\begin{definition}[Manifest API: update]\label{def:manifest-update}
\begin{lstlisting}[language=buzz1]
// /manifest

define function add *entry  
    to *node 
    on @path []byte 
has api PUT on "/manifest/<@node>"
    
as
    // if called on nil call on zero value
    @node = node{} if no @node 

    // if empty path then change entry field of node
    if no @path then
        @node entry = @entry
        return store @node

    // lookup the fork based on the first byte of path
    @fork = @node forks at head @path
    // if no fork yet, add the singleton node 
    if no @fork then
        @node forks at head @path =
            fork{@path, store node{@entry}}
        return store @node

    @common = prefix of @path and @fork prefix // common cannot be empty
    @rest = @fork prefix from @common length
    @newnode = node{}
    @newnode forks at head @rest = fork{@rest, @fork node}
    @midnode = self @entry to @newnode on @path from @common length 
    @node forks at head @path = fork{ @common, @midnode } 
    @node store
    

\end{lstlisting}
\end{definition}

\begin{definition}[Manifest API: remove]\label{def:manifest-remove}
\begin{lstlisting}[language=buzz1]
// /manifest

define function remove @path []byte 
    from *node
has api DELETE on "/manifest/<@node>/<@path>"
as
    // if called on nil call on zero value
    return node{} if no @node 

    // if empty path then change entry field of node
    if no @path then
        return nil if @node forks length == 0 
        @node entry = nil //entry exists
        return store @node

    // lookup the fork based on the first byte of path
    @fork = @node forks at head @path
    // if no fork yet, add the singleton node 
    return @node if no @fork

    @common = prefix of @path and @fork prefix // common cannot be empty
    return @node if @common and @fork prefix have different length          // path not found
    
    @rest = @fork prefix from @common length
    @newnode =  self @rest from @fork node               
    if no @newnode then           // deleted item was terminal node, delete fork 
        @node forks at head @res = nil
    else if @newnode forks length == 1 then // compact non-forking nodes 
        @singleton = @newnode forks first
        @newprefix = @common append @singleton prefix
        @node forks at head @path = 
            fork{ @newprefix, @singleton node }
    else
        @node fork at head @path node = @newnode
        
    @node store
    

\end{lstlisting}
\end{definition}


\begin{definition}[Manifest API:  merge]\label{def:manifest-merge}
\begin{lstlisting}[language=buzz1]
// /manifest

define function merge @new *node  
    to  @old *node 
has api POST on "/manifest/<@old:reference>/<@new:reference>"
as
    // if called on nil call on zero value
    return @new if no @old
    return @old if no @new
    @node = node{ @new or @old } 
    @new forks pos or @old forks pos 
        each bit @pos go 
            @fork = merge.fork @new forks at @pos
                to @old forks at @pos
            @node forks at @fork prefix head = @fork 
    @node store 

define function merge.fork @new fork 
    to @old fork    
as
    @common = prefix of @new prefix and @old prefix 
    @restnew = @new prefix from @common length
    @restold = @old prefix from @common length
    if no @restnew and no @restold then  
        return fork{@common, merge.node @new reference to @old reference}
    @node = add @new reference to nil on @restnew 
        add to @old reference @restold
    fork{ @common, @node }
         
\end{lstlisting}
\end{definition}
